package leetcode.editor.vscdev.greedy;

import java.util.Arrays;

public class lc134 {

}

class Solution {

    public int canCompleteCircuit(int[] gas, int[] cost) {
        return func2(gas, cost);
    }

    private int func3(int[] gas, int[] cost) {
        // 贪心，局部最优推出全局最优
        if (sum(gas) < sum(cost)) {// 总油量小于总花费,跑不完的
            return -1;
        }
        int curSum = 0;
        int start = 0;
        // 局部最优：当前累加rest[i]的和curSum一旦小于0，起始位置至少要是i+1，因为从i之前开始一定不行。
        for (int i = 0; i < cost.length; i++) {
            curSum += gas[i] - cost[i];
            if (curSum < 0) {
                curSum = 0;
                start = i + 1;
            }
        }
        return start;
    }

    private int func2(int[] gas, int[] cost) {
        // 全局最优模拟
        int curSum = 0;
        int min = Integer.MAX_VALUE; // 从起点出发，油箱里的油量最小值
        for (int i = 0; i < gas.length; i++) {
            int rest = gas[i] - cost[i];
            curSum += rest;
            if (curSum < min) {
                min = curSum;
            }
        }
        // 1.如果gas总和小于cost总和,那么不可能完成一圈
        if (curSum < 0) {
            return -1;
        }
        // 2.从0出发, 模拟后油没断过
        if (min > 0) {
            return 0;
        }
        // 3.从0以后出发, 哪个节点能把负数填平, 能填平的就是出发节点
        for (int i = gas.length - 1; i >= 0; i--) {
            int rest = gas[i] - cost[i];
            min += rest;
            if (min >= 0) {
                return i;
            }
        }
        return -1;

    }

    private int sum(int[] arr) {
        /*
         * if (arr == null) {
         * throw new IllegalArgumentException("输入的数组不能为 null");
         * }
         * 
         * int total = 0;
         * for (int g : arr) {
         * total += g;
         * }
         * return total;
         */
        return Arrays.stream(arr).sum();
    }

    @Deprecated
    private int func1(int[] gas, int[] cost) {
        // 暴力 超时pass
        for (int i = 0; i < gas.length; i++) {
            int currEngine = gas[i] - cost[i];// 剩余油量
            int index = (i + 1) % gas.length; // 下一个加油站
            // while循环适合模拟环形遍历
            while (currEngine >= 0 && index != i) {
                currEngine += gas[index] - cost[index];
                index = (index + 1) % gas.length;
            }
            // 如果能回到起点
            if (currEngine >= 0 && index == i) {
                return i;
            }
        }
        return -1;
    }
}